#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size();
        int middle = (left + right) / 2;
        while (left < right) {
            int midValue = nums[middle];
            if (midValue == target) return middle;
            if (midValue < target) {
                left = middle + 1;
            }
            if (midValue > target) {
                right = middle - 1;
            }
            middle = (left + right) / 2;
        }
        if (nums[left] == target) {
            return left;
        }
        return -1;
    }
};

int main() {
    Solution s;
    vector<int> v = {-1,0,3,5,9,12};
    cout << s.search(v, 9) << endl;
}